Lambda the Ultimate

Pickler Combinators, Andrew Kennedy 2004.

The tedium of writing pickling and unpickling functions by hand is relieved using a combinator library similar in spirit to the well-known parser combinators. Picklers for primitive types are combined to support tupling, alternation, recursion, and structure sharing. Code is presented in Haskell; an alternative implementation in ML is discussed.

This is a very pretty functional pearl, which is both useful and illustrates some nice semantic principles.

Sun recently announced JavaFX Script, a new Java-based scripting language designed for use with Sun's nascent rich interactive application development platform, JavaFX. JavaFX Script is statically typed, but it seems heavily influenced by dynamic languages like Python and JavaScript.

JavaFX Script provides an unusual declarative syntax intended to facilitate rapid interface development and it has some interesting features like support for first-class functions and Pythonic list comprehensions. The language also has some really unusual array manipulation operators that are somewhat thought provoking.

Here are a few samples to consider:

var titleTracks =
  select indexof track + 1 from album in albums,
    track in album.tracks where track == album.title;

select n*n from n in [1..100];

function factors(n) {
  return select i from i in [1..n/2] where n % i == 0;
}

x = [1,2,3];
insert 10 as first into x; // yields [10,1,2,3]
insert 6 after x[. == 2]; // yields [10,1,2,6,3]

You can also find some good examples of the declarative interface design syntax in Sun's JavaFX Script tutorial for Swing developers.

-- Ryan Paul

(via Wadler)

A visual LC game.

You can show it to the kids, or try to guess what each element in the game represents before reading the explanation at the end...

Raph Levien has posted an article The browser wars are once again upon us a few days ago to advogato, covering the current state of the landscape for client-side web programming, and ends by saying In any case, one thing seems clear, if surprising: the language of the future is JavaScript.

In recent years, there have been numerous proposals that introduce time into standard relational systems. Unfortunately, most of the attempts have been based on ad-hoc extensions of existing database systems and query languages, e.g., TQUEL and TSQL. Such extensions often create many problems, when precise semantics needs to be developed, if one exists at all. In a recent survey by J. Chomicki, a clean way of defining temporal databases based on logic was proposed. This methodology views temporal databases as multi-sorted, finitely representable first-order structures. Query languages then became formulas in suitable logics over the vocabulary of such structures.

The PLT Scheme folks now have a project blog.

The Expression Problem Revisited - Four new solutions using generics. Mads Torgersen. ECOOP'04.

...Over the years, many approaches to this problem have been proposed, each having different characteristics of type safety and reusability. While many of these rely on exotic or problem specific language extensions, this paper investigates the solution space within the framework of the soon-
to-be mainstream generic extensions of C# and the Java programming language.

Four new solutions are presented which, though quite different, all rely on techniques that can be used in everyday programming.

Same issue, same department (Daimi, Aarhus), different approaches.

Compared to the previous post, this paper is longer and thus perhaps easier to follow; the approach is more mainstream - and the code (in Java!) is downloadable.

Erik Ernst, The expression problem, Scandinavian style. MASPEGHI 2004.

This paper explains how higher-order hierarchies can be used to handle the expression problem. The expression problem is concerned with extending both the set of data structures and the set of operations of a given abstract data type. A typical object-oriented design supports extending the set of data structures, and a typical functional design supports extending the set of operations, but it is hard to support both in a smooth manner. Higher-
order hierarchies is a feature of the highly unified, mixin-based, extension-oriented kind of inheritance which is available in the language gbeta, which is itself a language that was created by generalizing the language Beta.

MASPEGHI, in case you wonder, stands for MechAnisms for SPEcialization, Generalization and inHerItance. On the site you'll also find the presentation related to the paper. And oh, gbeta is here.

I wonder what the Scala guys have to say about all this...

Shriram Krishnamurthi's excellent book, Programming Languages: Application and Interpretation (PLAI), long available in PDF form, is now available in paperback.

There's also a paid download available, "in case you want to reward the author in kind". A free PDF of the latest version is still available, which "really is the entire book, with no strings attached." The book is now licensed under a Creative Commons license which allows it to be adapted ("remixed") to fit a course.

Here's an overview of the book's approach:

This book unites two approaches to teaching programming languages, one based on a survey of languages and the other on writing definitional interpreters.

Each approach has significant advantages but also huge drawbacks. The interpreter method writes programs to learn concepts, and has at its heart the fundamental belief that by teaching the computer to execute a concept we more thoroughly learn it ourselves. While this reasoning is internally consistent, it fails to recognize that understanding definitions does not imply we understand the consequences of those definitions. For instance, the difference between strict and lazy evaluation, or between static and dynamic scope, is only a few lines of interpreter code, but the consequences of these choices is enormous. The survey of languages school is better suited to understand these consequences.

The book is used as the textbook for the programming languages course at Brown University, taken primarily by 3rd and 4th year undergraduates and beginning graduate (both MS and PhD) students. It seems very accessible to smart 2nd year students too. The book has been used as a textbook at over a dozen other universities as a primary or secondary text.

Don Stewart has collected (all?) the Functional Pearls from JFP, ICFP, and elsewhere onto http://www.haskell.org/haskellwiki/Research_papers/Functional_pearls. Most of the are available online and are linked to from here. If you know what a Functional Pearl is, then you will enjoy this page, if not, you are in for a treat. Finally, if you know where any of the offline ones are publically available on the internet, that would be useful (just update the page).